package com.xyzwps.collections.list;

import com.xyzwps.collections.List;
import com.xyzwps.collections.Pair;

import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.Objects;

/**
 * 这是一个基于双链表的 List 实现。
 *
 * @param <E> 列表中的元素类型
 */
public class LinkedList<E> implements List<E> {
    private final Node root = new Node(null, null, null);
    private Node last = root;
    private int size = 0;
    private int modi = 0;

    @Override
    public void addAll(E[] elements) {
        Objects.requireNonNull(elements);
        if (elements.length == 0) return;

        this.modi++;
        for (E element : elements) {
            Node node = new Node(element, this.last, null);
            this.last.next = node;
            this.last = node;
        }
        this.size += elements.length;
    }

    @Override
    public void add(E element) {
        this.modi++;
        Node node = new Node(element, this.last, null);
        this.last.next = node;
        this.last = node;
        this.size++;
    }

    @Override
    public E getAt(Integer index) {
        this.checkIndex(index);
        return this.findNodeByIndex(index).element;
    }

    private void checkIndex(int index) {
        if (index < 0 || index >= this.size()) {
            throw new IndexOutOfBoundsException("Index " + index + " out of bounds");
        }
    }

    @Override
    public void putAt(Integer index, E element) {
        this.modi++;
        checkIndex(index);
        this.findNodeByIndex(index).element = element;
    }

    private Node findNodeByIndex(int index) {
        Node curr = this.root;
        for (int i = 0; i <= index; i++)
            curr = curr.next;
        return curr;
    }

    @Override
    public void insertAt(int index, E element) {
        this.modi++;
        checkIndex(index);
        Node curr = this.findNodeByIndex(index);
        Node prev = curr.prev;
        Node node = new Node(element, prev, curr);
        curr.prev = node;
        prev.next = node;
        this.size++;
    }

    @Override
    public E removeAt(int index) {
        this.modi++;
        checkIndex(index);
        Node curr = this.findNodeByIndex(index);
        this.removeNode(curr, index);
        return curr.element;
    }

    // 这里假定 node 和 index 是对应的
    private void removeNode(Node node, int index) {
        Node prev = node.prev;
        Node next = node.next;
        if (index == this.size - 1) {
            prev.next = null;
            this.last = prev;
        } else {
            prev.next = next;
            next.prev = prev;
        }
        this.size--;
    }

    @Override
    public int removeFirst(E element) {
        this.modi++;
        Pair<Node, Integer> pair = this.findElement(element);
        if (pair.right > -1) {
            this.removeNode(pair.left, pair.right);
        }
        return pair.right;
    }

    @Override
    public int indexOf(E element) {
        return this.findElement(element).right;
    }

    private Pair<Node, Integer> findElement(E element) {
        Node curr = this.root;
        for (int i = 0; curr.next != null; i++) {
            curr = curr.next;
            if (Objects.equals(curr.element, element))
                return Pair.of(curr, i);
        }
        return Pair.of(null, -1);
    }

    @Override
    public void clear() {
        this.modi++;
        this.root.next = null;
        this.last = root;
        this.size = 0;
    }

    @Override
    public boolean has(E element) {
        Pair<Node, Integer> pair = findElement(element);
        return pair.right > -1;
    }

    @Override
    public int size() {
        return this.size;
    }

    @Override
    public Iterator<E> iterator() {
        return new Itr(this);
    }

    private class Itr implements Iterator<E> {
        Node curr;
        LinkedList<E> list;
        int expectedModi;

        Itr(LinkedList<E> list) {
            this.list = list;
            this.curr = list.root;
            this.expectedModi = list.modi;
        }

        @Override
        public boolean hasNext() {
            checkForComodification();
            return curr.next != null;
        }

        @Override
        public E next() {
            checkForComodification();
            curr = curr.next;
            return curr.element;
        }


        final void checkForComodification() {
            if (expectedModi != list.modi)
                throw new ConcurrentModificationException();
        }

    }

    private class Node {
        E element;
        Node prev, next;

        Node(E e, Node p, Node n) {
            this.element = e;
            this.prev = p;
            this.next = n;
        }
    }
}
